package Hard;

import java.util.*;

public class Prefixsum {

    /**
     * 一维情况下 class NumArray {
     * 
     * ArrayList<Integer> num = new ArrayList<Integer>();
     * 
     * public NumArray(int[] nums) { this.num.add(0); int sum = 0; for (int i = 0; i
     * < nums.length; ++i) { sum += nums[i]; this.num.add(sum); } }
     * 
     * public int sumRange(int left, int right) { return this.num.get(right + 1) -
     * this.num.get(left); } }
     */
    class NumArray {

        private int[] sum;

        public NumArray(int[] nums) {
            sum = new int[nums.length + 1]; // 多一个sum[0] = 0，因为一个元素都没有时相加和为0
            for (int i = 0; i < nums.length; i++) {
                sum[i + 1] = sum[i] + nums[i];
            }
        }

        // sum[i,j] = sum[j+1] - sum[i]
        public int sumRange(int i, int j) { // 前面某一部分的和就等于差值
            return sum[j + 1] - sum[i];
        }

    }

    // 二维情况下，要学会抽象成一维, 固定某一方向（行或者列），然后再进行前缀和的计算
    class NumMatrix {

        private int[][] sumMatrix;

        public NumMatrix(int[][] matrix) {
            int row = matrix.length, col = matrix[0].length; // row矩阵行数,col列数
            sumMatrix = new int[row][col + 1];
            for (int i = 0; i < row; ++i) { // 固定列，逐行相加
                for (int j = 0; j < col; ++j) {
                    sumMatrix[i][j + 1] = sumMatrix[i][j] + matrix[i][j]; // 每一列等于前一列加上矩阵当前列的和
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            int res = 0;
            for (int i = row1; i <= row2; ++i) { // 再逐行对列的差进行计算
                res += (sumMatrix[i][col2 + 1] - sumMatrix[i][col1]);
            }
            return res;
        }
    }

    public static void main(String args[]) {
        int[][] matrix = { { 1, 0, 1 }, { 0, -2, 3 } };
        int k = 2;
        System.out.println(maxSumSubmatrix(matrix, k));

    }

    // 官方题解
    public static int maxSumSubmatrix(int[][] matrix, int k) {
        int ans = Integer.MIN_VALUE;
        int m = matrix.length, n = matrix[0].length;
        for (int i = 0; i < m; ++i) { // 枚举上边界
            int[] sum = new int[n];
            for (int j = i; j < m; ++j) { // 枚举下边界
                for (int c = 0; c < n; ++c) {
                    sum[c] += matrix[j][c]; // 更新每列的元素和
                }
                TreeSet<Integer> sumSet = new TreeSet<Integer>();
                sumSet.add(0);
                int s = 0;
                for (int v : sum) {
                    s += v;
                    Integer ceil = sumSet.ceiling(s - k);
                    if (ceil != null) {
                        ans = Math.max(ans, s - ceil);
                    }
                    sumSet.add(s);
                }
            }
        }
        return ans;
    }

    // 暴力+动态dp+状态压缩+滚动数组
    public int maxSumSubmatrix2(int[][] matrix, int k) {
        int rows = matrix.length, cols = matrix[0].length, max = Integer.MIN_VALUE;
        // O(cols ^ 2 * rows)
        for (int l = 0; l < cols; l++) { // 枚举左边界
            int[] rowSum = new int[rows]; // 左边界改变才算区域的重新开始
            for (int r = l; r < cols; r++) { // 枚举右边界
                for (int i = 0; i < rows; i++) { // 按每一行累计到 dp
                    rowSum[i] += matrix[i][r];
                }
                max = Math.max(max, dpmax(rowSum, k));
                if (max == k)
                    return k; // 尽量提前
            }
        }
        return max;
    }

    // 在数组 arr 中，求不超过 k 的最大值
    private int dpmax(int[] arr, int k) {
        int rollSum = arr[0], rollMax = rollSum;
        // O(rows)
        for (int i = 1; i < arr.length; i++) {
            if (rollSum > 0)
                rollSum += arr[i];
            else
                rollSum = arr[i];
            if (rollSum > rollMax)
                rollMax = rollSum;
        }
        if (rollMax <= k)
            return rollMax;
        // O(rows ^ 2)
        int max = Integer.MIN_VALUE;
        for (int l = 0; l < arr.length; l++) {
            int sum = 0;
            for (int r = l; r < arr.length; r++) {
                sum += arr[r];
                if (sum > max && sum <= k)
                    max = sum;
                if (max == k)
                    return k; // 尽量提前
            }
        }
        return max;
    }
}